function ListNode(params) {
  this.val = params
  this.next = null
}
let a = new ListNode(5)
let b = new ListNode(4)
let c = new ListNode(3)
let d = new ListNode(2)
let e = new ListNode(1)

a.next = b
b.next = c
c.next = d
d.next = e
e.next = null

/**
206 反转链表
 */

// function reverse(head) {
//     if(!head.next) return head
//     let prev =null
//     let curr = head;
//     while (curr!= null) {
//         let next = curr.next;
//         curr.next = prev; //进行交换 5=》4
//         prev = curr;//进行交换 4=》5
//         curr = next;
//     }
//     return prev
// }

// let a = new ListNode(5)
// let b = new ListNode(4)
// let c = new ListNode(3)
// let d = new ListNode(2)
// let e = new ListNode(1)

// a.next = b
// b.next = c
// c.next = d
// d.next = e
// e.next = null

// // console.log(reverse(a))

// /**
//     92
//  */
// /**
//  * Definition for singly-linked list.
//  * function ListNode(val) {
//  *     this.val = val;
//  *     this.next = null;
//  * }
//  */
// /**
//  * @param {ListNode} head
//  * @param {number} m
//  * @param {number} n
//  * @return {ListNode}
//     输入: 1->2->3->4->5->NULL, m = 2, n = 4
//     输出: 1->4->3->2->5->NULL
//  */
// var reverseBetween = function(head, m, n) {
//     let i = 0 //第一个指针
//     let j = 0
//     let curr = head
//     while (curr != null) {
//         let next = curr.next 
//         if(i>=m && i<=n){

//             j++
//         }else{
//             i++
//             j++
//         }
//         curr = next

//     }
// };

// console.log(reverseBetween(a,2,4))

/**
141 环形链表
    暴力法： 是否有null --
    建立一个map表去对应，看是否有，O(n)
    快慢指针法，fast+2，slow+1 当快指针等于慢指针相遇了O(n) --龟兔赛跑法
 */
//  var hasCycle = function(head) {
//     let fast = head.next
//     let slow = head;

//     while(fast && slow && head.next){
//         slow = slow.next
//         fast = fast.next
//         if(slow.val == fast.val){
//             return true
//         }
//     }
//     return false
// };

// var hasCycle = function(head) {
//     let fast = head.next
//     let slow = head;

//     while(fast && slow && head.next){
//         slow = slow.next
//         fast = fast.next
//         if(slow.val == fast.val){
//             return true
//         }
//     }
//     return false
// };
/**
 * @param {string} s
 * @return {boolean}
 */
// var isValid = function(s) {
//     let map ={
//         '{':'}',
//         '[':']',
//         '(':')'
//     }
//     let stack =[]
//     for(let i=0;i<s.length;i++){
//         debugger
//         if(s[i] in map){
//             stack.push(s[i])
//         }else{
//             if(s[i] != map[stack.pop()]) return false

//         }

//     }
//     return stack.length === 0 ? true : false
// };

// isValid('()')

/**
//  * @param {number} k
//  * @param {number[]} nums
//  */
// var KthLargest = function(k, nums) {
//     this.kth = k
//     this.stack = []
// };

// /** 
//  * @param {number} val
//  * @return {number}
//  703号
//  交换数组中的元素 a,b => arr[a] = arr.splice(b, 1, arr[a])[0]
//  关于splice()后的 [0] ,是因为splice的返回值是数组类型，加上[0]是取数组中的元素
//  */
// KthLargest.prototype.add = function(val) {

// };

// const kthLargestElement = function (k, nums, start, end) {
//     var low = start;
//     var high = end;
//     var temp = nums[low];       //枢轴点 一开始就是第一位

//     while(low < high){
//         while(low<high && nums[high]<=temp){
//             high--;
//         }
//         //在高位遇到比temp大的值交换到低位
//         nums[low] = nums.splice(high, 1, nums[low])[0];
//         while(low<high && nums[low]>=temp){
//             low++;
//         }
//         //在低位遇到比temp小的值交换到高位
//         nums[high] = nums.splice(low, 1, nums[high])[0];
//     }
//     //枢轴点回到原位
//     nums[high] = temp;

//     if(high == k-1){
//         return  temp;       //当前枢轴点即所求
//     }else if(high > k-1){
//         return  kthLargestElement(k, nums, start, high-1);
//     }else{
//         return  kthLargestElement(k, nums, high+1, end);
//     }
// }

// var KthLargest = function(k, nums) {
//     this.kth = k
//     this.stack = [] // 这个数组是一个从大到小排列的数组，最后一位就是第k位的值
//     this.shiftUp = (num) => {
//         debugger
//         let len = this.stack.length
//         if (len === 0) {
//             this.stack.push(num)
//         } else if (num >= this.stack[0]) { //如果当前值大于第一个值，则直接放入
//             this.stack.unshift(num)
//             if (len + 1 > this.kth) {
//                 this.stack.pop()
//             }
//         } else if (num <= this.stack[len - 1]) { //当前值不小于 stack的最后一位 ，说明 this。stack需要维护了，需要做替换了
//             if (len < this.kth) {
//                 this.stack.push(num)
//             }
//         } else {
//             let lb = 0, rb = len - 1, i = rb, dir = 0// lb 起始，rb 最后一位，i等于最后一位，dir？
//             while (lb !== rb) { //左边指针不等于右边指针
//                 if (dir === 1 && i === rb) { //如果dir 为1 ，且 i为rb 
//                     i = rb - 1 // i为右边指针-1
//                     rb = i //rb = i
//                     lb = i // lb也为i ？？？？
//                 } else if (dir === -1 && i === lb) { //？？？
//                     i = lb
//                     rb = i
//                     lb = i
//                 } else if (num > this.stack[i]) {
//                     // 左移
//                     rb = i
//                     i = Math.floor((lb + rb) / 2)
//                     dir = -1
//                 } else if (num < this.stack[i]) {
//                     // 右移
//                     lb = i
//                     i = Math.ceil((lb + rb) / 2)
//                     dir = 1
//                 } else {
//                     lb = i
//                     rb = i
//                 }
//             }
//             this.stack.splice(i + 1, 0, num)
//             if (len + 1 > this.kth) {
//                 this.stack.pop()
//             }
//         }
//     }
//     nums.forEach(this.shiftUp)
// };

// KthLargest.prototype.insert = function (index, val) {
//     this.stack.splice(index, 0, val)
//     if (this.stack.length > this.kth) {
//         this.stack.pop()
//     }
// }

// KthLargest.prototype.add = function(val) {
//     this.shiftUp(val)
//     return this.stack[this.kth - 1]
// };

// let k = 3;
// let arr = [4,5,8,2];
// let kthLargest = new KthLargest(k, arr);
// kthLargest.add(3)
// kthLargest.add(5)
// kthLargest.add(10)
// kthLargest.add(9)
// kthLargest.add(4)


/*
    239 滑动窗口  最大值
*/
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 维护双端队列
 */
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
// var maxSlidingWindow = function(nums, k) {
//     let n = nums.length;
//     class slideWindow{
//         constructor(){
//             this.data = []; //双端队列
//         }
//         push1(val){ //只要新加进来的值大于前面的值，前面的全部删掉
//             let data = this.data;
//         debugger
//             while(data.length > 0 && data[data.length - 1] < val){ //每次push元素时，将队列中更小元素删除，直到不小时
//                 data.pop();
//             }
//             data.push(val);
//         }
//         pop1(val){ //传进来的是当然窗口的第一位了 如果和 data的第一位是一样的，说明窗口要挪动了，把第一位shift出去
//             let data = this.data;
//             debugger
//             if(data.length > 0 && data[0] === val){ //每次pop元素时，如果是更小的元素在push时就已经删除了，只需要判断是否是头部最大值，是再删除一遍头部元素即可
//                 data.shift(); //对首弹出
//             }
//         }
//         max1(){ //队列的第一位就是当前窗口中的最大值
//             return this.data[0];
//         }
//     }
//     let res = [];
//     let win = new slideWindow();
//     for(let i = 0;i < n;i++){
//         if(i < k - 1){
//             win.push1(nums[i]);
//         }else{
//             win.push1(nums[i]);
//             res.push(win.max1());
//             win.pop1(nums[i - k + 1]);
//         }
//     }
//     return res;
// };

// let nums = [1,3,-1,-3,5,3,6,7]
// let k = 3

// maxSlidingWindow(nums,k)

// var isAnagram = function(s, t) {
//     let map1 = new Map()
//     debugger
//     for(let i = 0; i< s.length;i++){
//         if(map1.has(s[i])){
//             let val = map1.get(s[i])
//             val = val +1
//             map1.set(s[i],val)
//         }else{
//             map1.set(s[i],1)
//         }

//     }
//     for(let i = 0; i< t.length;i++){
//         if(map1.has(t[i])){
//             let val = map1.get(t[i])
//             val = val-1
//             if(val>=0){
//                 map1.set(t[i],val)
//             }else{
//                 return false
//             }
//       }else{
//             return false
//         }
//     }
//     return true
// };

// isAnagram('anagram','nagaram')

/**
 * @param {number[]} nums
 * @return {number[][]}
 15 三数之和 map
 nums = [-1, 0, 1, 2, -1, -4]，
 [
  [-1, 0, 1],
  [-1, -1, 2]
]
[
    [0,1,-1],
    [0,-1,1],
    [1,-1,0],
    [2,-1,-1]
]
 */
// var threeSum = function(nums) {
//     //如果三个数都是大于0或者都小于0，则不可能
//     //暴力法
//     let result =[]
//     let set = new Set()
//     for(let i=0;i<nums.length;i++){
//         for(let j=i+1;j<nums.length-1;j++){
//             let c = -(nums[i]+nums[j])
//             set.add([nums[i],nums[j],c]) 

//         }
//     }
//     return result
// };

// var threeSum = function(nums) {
//     let sortNums = nums.sort((a, b) => a - b)
//     let result =[]
//     for(let i= 0; i<sortNums.length-2;i++){
//         if(i >= 1 && sortNums[i] === sortNums[i-1]) {
//             continue
//         }
//         let first = i+1
//         let last = sortNums.length -1 
//         while(first < last){
//             let sum = nums[i] + nums[first] + nums[last]
//             if(sum === 0){ 
//                 result.push([sortNums[i] , sortNums[first] , sortNums[last]])
//                 first++
//                 while(sortNums[first]===sortNums[first-1]){
//                     first++
//                 }
//             }else if(sum < 0){ //太小了，向右移动
//                 first++
//             }else if(sum >0){ 
//                 last--      
//             }
//         }

//     }
//     return result
// }
// console.log(threeSum([-1,0,1,2,-1,-4]))

/**
    66.加一
 */

// var plusOne = function(digits) {
//     let len = digits.length
//     let cur = 0
//     for( let i = len  ;i >0 ; i--){
//         if(digits[i] + 1 >9){ //如果大于9，就直接变成0 ，等到1===0的时候，把第一位插入1就好了 妙啊
//             digits[i] = 0;
//             if(i==0){
//                 // 数组首项置1
//                digits.unshift(1);
//                return digits;
//             }
//         }else{
//            digits[i]++ //尾巴加1后，直接断开循环 返回出去
//            return digits
//         }
//     }
// };

// plusOne([1,2,3]) //[99]

/**
    498.对角遍历
 * @param {number[][]} matrix
 * @return {number[]}
 */
// var findDiagonalOrder = function(matrix) {
//     /**
//         [1,2,3]
//         [4,5,6]
//         [7,8,9]

//         矩阵为 m为列+n为行 m =3 ,n = 3 
//         据题意可知，当m+n为奇数时向下遍历，m+n为偶数时向上遍历
//         // 遍历方式
//         // 向上遍历时：m递减，n递增
//         // 向下遍历时：m递增，n递减
//         // 以此循环

//          遍历结束条件
//         *  向上遍历：m递减到0或者n递增到最大值
//         *  向下遍历：n递减到0或者m递增到最大值
//      */

//      // 初始化返回值
//     let res = [];
//     let m = matrix.length;
//     // 判断输入值长度为0直接返回
//     if (m === 0 || (m > 0 && matrix[0].length === 0)) return res; //二维数组为空，或者为1维数组直接返回
//     let n = matrix[0].length;
//     // 定义Boolean traversal值为此时的遍历方式为向上还是向下
//     let traversal = true;
//     for (let i = 0; i < m + n - 1; i++){
//         let pm = traversal ? m : n;
//         let pn = traversal ? n : m; 
//         // 保证了x + y = i
//         let x = (i < pm) ? i : pm - 1;
//         let y = i - x; 
//         while( x >= 0 && y < pn ){
//             res.push(traversal ? matrix[x][y] : matrix[y][x]);
//             x--
//             y++
//         }
//         traversal = !traversal;
//     }
//     return res
// };

/**
    方法二 定义4个方向 横向右，斜向左，竖向下 ，斜向上
 */
// var findDiagonalOrder = function(matrix) {


//      // 初始化返回值
//     let res = [];
//     let m = matrix.length;
//     if(m === 0 || (m >0 matrix[0].length === 0)){ return res }


//     return res
// };
// findDiagonalOrder([[1,2,3],[4,5,6],[7,8,9]])

/**
    54.螺旋矩阵
 */

/**
* @param {number[][]} matrix
* @return {number[]}
   第一行可以直接输出， 可以使用递归
   [1,2,3]
   [4,5,6]
   [7,8,9]
*/
// var spiralOrder = function(matrix){

//     //处理每一圈数据遍历的过程 matrix矩阵 r为上一次返回的矩阵
//     let deep = (matrix,r=[])=>{ 
//         for(let i = 0,len = matrix.length; i < len; i++){
//             if(i === 0){
//                 r = r.concat(matrix[i])
//             }else if(i === len -1){
//                 r = r.concat(matrix[i].reverse())
//             }else{
//                 if (matrix[i].length) {
//                     r.push(matrix[i].pop())
//                 }
//             } 
//         }
//         matrix.shift()
//         matrix.pop()

//         for(let j= matrix.length -1; j>0; j--){
//             if (matrix[j].length) {
//                 r.push(matrix[j].shift())
//             }
//         }

//         if(matrix.length){
//             return deep(matrix,r)
//         }else{
//             return r
//         }
//     }

//     return deep(matrix,[])
// };




// spiralOrder([[1,2,3],[4,5,6],[7,8,9]])


/*
    25.二进制求和
// */
// var addBinary = function(a, b) {
//     let alen = a.length -1,
//         blen = b.length -1,
//         res='',
//         cur=0;

//     while(alen>=0||blen>=0||cur){
//         let x= +a[alen] || 0
//         let y= +b[blen] || 0
//         let sum = x + y + cur;
//             res = sum%2 + res
//             cur = sum >1
//         alen--
//         blen--
//     }
//     return res
// };
// addBinary('1010','1011')


// /**
//     28题实现 strStr()
//     sunday算法
//     解决线性字符串的算法，尽可能的去跳跃过滤不匹配的字符串，而不是一般的解法，一个一个的去循环匹配
//     滑动窗口 模型

//  */

//  /**
//  * @param {string} haystack
//  * @param {string} needle
//  * @return {number}
//     haystack = "hello", needle = "ll"
//  */
// var strStr = function(haystack, needle) {
//     //边界的判断
//      const needleLen = needle.length
//      const haylen = haystack.length
//      //如果需要匹配的字符串长度比原本字符串还长，那不符合返回-1
//     if(needleLen > haylen){
//         return -1
//     }
//     //如果为空，返回值应该为0
//     if(needleLen === 0){
//         return 0
//     }

//     let initailOffsetMap = ()=>{
//         //这里建立了一个映射表
//         //偏移表告诉我们下一步可能匹配需要移动的最小步数。
//         const offsetMap = {}
//         for (let i = 0; i < needleLen; i++) {
//             offsetMap[needle[i]] = needleLen - i
//         }
//         return (s)=>{
//             return offsetMap[s] || needleLen
//         }
//     }

//     const getOffset = initailOffsetMap()

//     let i = 0
//     while( i <= haylen - needleLen){
//         let temp = 0

//          for (let j = 0; j < needleLen; j++) { //循环needle去和haystack匹配，只要一个不满足，跳出循环
//             if (haystack[i + j] === needle[j]) temp++
//             else break
//         }

//         if (temp != needleLen){
//             //否则我们要计算下一次的开始位置
//             let ss = haystack[i + needleLen]
//              i += getOffset(ss)
//         }else{
//             return i
//         }
//     }
//     return -1
// };

// console.log(strStr('a','a'))

/**
    14.最长公共前缀
 */

//  var longestCommonPrefix = function(strs) {
//     let first = strs.shift() //取出来第一个当目标字符串
//     //每一次循环的时候如果没有那就删除1位 知道
//     for(let i =1;i<strs.length;i++) {
//         let j=0;
//         for(;j<first.length && j < strs[i].length;j++) {
//             debugger
//             if(first[j] != strs[i][j])
//                 break;
//         }
//         first = first.substr(0, j);
//         if(first === "")
//             return first;
//     }
//     return first
// };
// var longestCommonPrefix = function(strs) {
//     if (!strs.length) {
//         return ''
//     }

//     let commonStr = strs[0]

//     for (let i = 1; i < strs.length; i++) {
//         while (strs[i].indexOf(commonStr) != 0) { //妙啊！最后commor变成“空” indexof就会变成 0，然后退出循环
//             commonStr = commonStr.substring(0, commonStr.length - 1)//每一次都让这个字符串变短-1
//         }
//     }
//     return commonStr
// }
// longestCommonPrefix(["a","b"])

/**
     344. 反转字符串 反转字符串
     双指针
 */

/**
     344. 数组拆分 I
     双指针
 */

// var minSubArrayLen = function(s, nums) {
//   if (nums.length === 0) return 0;
//   const slideWindow = [];
//   let acc = 0;
//   let min = null;

//   for (let i = 0; i < nums.length + 1; i++) {
//     const num = nums[i];

//     while (acc >= s) {
//       if (min === null || slideWindow.length < min) {
//         min = slideWindow.length;
//       }
//       acc = acc - slideWindow.shift();
//     }

//     slideWindow.push(num);

//     acc = slideWindow.reduce((a, b) => a + b, 0);
//   }

//   return min || 0;
// };

/**
//  * @param {number} s
//  * @param {number[]} nums
//  * @return {number}
//  */
// var minSubArrayLen = function(s, nums) {

//     if(nums.length === 0){
//             return 0
//      }

//     if(nums.length === 1){
//         return nums[0] >s ?nums.length :0
//      }

//     if(nums.length ===2){
//             return nums[0] +nums[1] >s ? nums.length : 0
//        }

//     let k = 2;
//     let minlegnth = nums.length 

//     for(let i= 0; i < nums.length -2 ;i++){
//         while( k<= nums.length -2 ){
//             let sum = nums.slice(i,k).reduce((s,c)=>{return s+c})
//               if( sum < s){
//                 k++
//              }else{
//                  minlegnth = Math.min(minlegnth,k)
//                  k = i+2
//                  break;
//              }
//         }

//     }

//     return minlegnth      
// };
// minSubArrayLen(7,[2,3,1,2,4,3])

/**
 *   189 旋转数组
 */

// var rotate = function(nums, k) {
//     while(k>0){
//         //将最后一位和第一位交换
//         let temp = nums.pop()
//         nums.unshift(temp)
//         k--
//     }
//     return nums
// };

// var rotate = function(nums, k) {
//     let temp = nums.splice( k + 1)
//         nums = temp.reverse().concat(nums)
//     return nums
// };
// var rotate = function(nums, k) {
//     console.log(...nums.splice(nums.length - k))
//     return nums.splice(0, 0, ...nums.splice(nums.length - k));
// };
// console.log(rotate([1,2,3,4,5,6,7],3))


/**
 * @param {number} rowIndex
 * @return {number[]}
  杨辉三角 II 119
 */
/**
 * @param {number} rowIndex
 * @return {number[]}
 */
// var getRow = function(rowIndex) {
//     let res = [];
//     for (let i = 0; i <= rowIndex; i++) {
//         if (i <= 1) {
//             res.push(1);
//         } else {
//             for (let j = 1; j <= i; j++) {
//                     if (j === 1) {
//                         res.splice(j, 0, res[j-1]+res[j])
//                         j++;
//                     } else {
//                         res.splice(j-1, 1, res[j-1]+res[j])
//                     }
//             }
//         }
//     }
//     return res;
// };

// console.log(getRow(3))

// var reverseWords = function(s) {
//     let arr = s.split(' ')
//     let res = []
//     for(let i = 0 ; i<arr.length; i++){
//       debugger
//         let str = arr[i].split('').reverse().join('')
//         res.push(str)
//     }

//     return res.join(' ')
// };



// var reverseWords = function(s) {
// let result = ''
//     let word = ''
//     for (const c of s) {
//         if (c === ' ') {
//             result += word + ' '
//             word = ''
//         } else {
//             word = c + word
//         }
//     }
//     return result + word
// };
// console.log(reverseWords("Let's take LeetCode contest"))

/**
 * @param {number[]} nums
 * @return {number}
 */
// var removeDuplicates = function(nums) {
//     let k =1;
//     for(let i = 0; i<nums.length-1;i++){
//         if(nums[i] === nums[k]){
//            nums.splice(k,1)
//            k++
//          }
//     }
//     return nums
// };

// var removeDuplicates = function(nums) {
//     for(let i = 0; i<nums.length;i++){
//         for(let j = 1; j<nums.length;j++){
//           debugger
//             if(nums[i] === nums[j]){
//                 nums.splice(j,1)
//             }
//         }
//     }
//     return nums
// };

// var removeDuplicates = function(nums) {
//     let index = 0
//     for( let i=0,len=nums.length; i<len; i++ ){
//         if( nums[i] != nums[i+1] ) {
//             nums[index] = nums[i]
//             index++
//         }
//     }
//     return index
// };

// removeDuplicates([1,1])

// var moveZeroes = function(nums) {
//     let i = 0, j=0
//     while(i < nums.length){
//         if (nums[i] != 0){
//             if (j < i){
//                 nums[j] = nums[i]
//                 nums[i] = 0
//             }
//             j++
//         }
//         i++
//     }
//     return nums
// };



// moveZeroes([0,0,1])

// var maxProfit = function(prices) {
//     let max=0;
//     let cur=0;
//     let temp=0
//     for(let i=0,len=prices.length;i<len;i++){
//     //   if(prices[i+1] !=undefined){
//     //     //如果当前的价格比手上的高卖出，当前没有则买入
//     //     let min = Math.min(prices[i],prices[i+1]) || 0
//     //     if(cur === 0 && min){
//     //         cur = min
//     //     }else if(cur < prices[i]){
//     //         max += prices[i] - cur
//     //         cur = 0
//     //     }
//     //   }    
//     }
//     return max
// };

// maxProfit([1,2,3,4,5])


/**
 * @param {number[]} nums
 * @return {boolean} 判断是否有重复
 */
// var containsDuplicate = function(nums) {
//     //暴力法 o(n2)
//     if(nums.length === 1){
//         return false
//     }
//     for(let i = 0 ,len = nums.length ; i < len ; i++){
//         for( let j = i+1 ,len = nums.length ; j<len ; j++){
//             if( nums[i] === nums[j]){
//                 return true
//             }
//         }
//     }
//     return false
// }
// var containsDuplicate = function(nums) {
//     //map o(n)
//     let map = new Map()
//     for(let i = 0 ,len = nums.length; i< len ; i++){
//         if(map.has(nums[i])){
//             return true
//         }
//         map.set(nums[i],1)
//     }
//     return false
// }

/**
 * @param {number[]} nums
 * @return {number}
 */
// var singleNumber = function(nums) {
//     // map 
//     let map = new Map()

//     for(let i = 0, len = nums.length ; i<len;i++ ){
//         if(map.has(nums[i])){
//             let item = map.get(nums[i])
//             map.set(nums[i],item+1)
//         }else{
//             map.set(nums[i],1)
//         }

//     }
//     for (let [key, value] of map.entries()) {
//         if(value === 1){
//             return key
//         }
//     }

//     return 0
// };

// var singleNumber = function(nums) {
//     //判断map里时候有值 有的话
//     const obj = {}
//     for(let i=0;i<nums.length;i++) {
//         if(obj[nums[i]]) {
//             delete obj[nums[i]]
//         } else {
//             obj[nums[i]] = 1
//         }
//     }
//     return Object.keys(obj)[0]
// }
// var singleNumber = function(nums) {
//     let num = 0
//         for(let i=0;i<nums.length;i++) {
//             num = num ^ nums[i] //学到了 相同的数用^会变成0 其实就是消掉了，空间度也是最小的
//         }
//         return num
// }
// console.log(singleNumber([2,2,1,1,3,3,4]))

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
// var intersect = function(nums1, nums2) {
//     if(nums1.length > nums2.length) [nums1,nums2] = [nums2,nums1];
//     let hash = {};
//     for(let i = 0;i < nums1.length;i++){
//         if(hash[nums1[i]]){
//             hash[nums1[i]]++;
//         }else{
//             hash[nums1[i]] = 1;
//         }
//     }
//     let r = 0;
//     for(let i = 0;i < nums2.length;i++){
//         if(hash[nums2[i]]){
//             nums1[r++] = nums2[i];
//             hash[nums2[i]]--;
//         }
//     }
//     return nums1.slice(0,r);
// };

// var intersect = function (nums1,nums2) {
//     nums1 = nums1.sort((a,b) => a - b);
//     nums2 = nums2.sort((a,b) => a - b);
//     let i = 0;
//     let j = 0;
//     let k = 0;

//     while( i<nums1.length && j< nums2.length){
//         if(nums1[i] < nums2[j]){
//             i++
//         }else if(nums1[i] > nums2[j]){
//             j++;
//         }else{
//             nums1[k++] = nums1[i];
//             i++;
//             j++;
//         }

//     }
//     return nums1.slice(0,k);
// }

// var intersect = function(num1,num2){
//     const intersection = [];
//     for(let i = 0; i < nums1.length; i++) {
//         let j = nums2.indexOf(nums1[i]); //如果有，就拿出来然后删除
//         if(j > -1) {
//         intersection.push(nums2.splice(j,1)[0]);
//         }
//     }
//     return intersection;
// }

// console.log(intersect([4,9,5],[9,4,9,8,4]))

/**
 * @param {character[][]} board
 * @return {boolean} 有效数独
 * [
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]

 */
// var isValidSudoku = function(board) {
//     //hash map
//     var row = {}
//     var columns = {}
//     var boxes = {}

//     for(let i = 0;i < 9;i++){
//         for(let j = 0;j < 9;j++){
//             let num = board[i][j]
//             if( num != '.'){
//                 // 子数独序号
//                 let boxIndex = parseInt((i/3)) * 3 + parseInt(j/3);
//                 if(rows[i+'-'+num] || columns[j+'-'+num] || boxes[boxIndex+'-'+num]){
//                     return false
//                 }
//                 row[i+'-'+num] = true
//                 columns[j+'-'+num] = true
//                 boxes[boxIndex+'-'+num] = true
//             }
//         }
//     }

//     return true
// };

// isValidSudoku([ 
//     ["5","3",".",".","7",".",".",".","."],
//     ["6",".",".","1","9","5",".",".","."],
//     [".","9","8",".",".",".",".","6","."],
//     ["8",".",".",".","6",".",".",".","3"],
//     ["4",".",".","8",".","3",".",".","1"],
//     ["7",".",".",".","2",".",".",".","6"],
//     [".","6",".",".",".",".","2","8","."],
//     [".",".",".","4","1","9",".",".","5"],
//     [".",".",".",".","8",".",".","7","9"]
//  ])

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 * 旋转图片
 */
// var rotate = function(matrix) {
// let n = matrix.length;

// transpose matrix 
/**
 * [
        [ 5, 1, 9,11],          [5,2,13,15]
        [ 2, 4, 8,10],   =====> [1,4,3,114]
        [13, 3, 6, 7],   =====> [9,8,6,12]
        [15,14,12,16]           [11,10,7,16]
    ]
 */
// for (let i = 0; i < n; i++) {
//     for (let j = i; j < n; j++) {
//         let tmp = matrix[j][i];
//         matrix[j][i] = matrix[i][j];
//         matrix[i][j] = tmp;
//     }
// }
// reverse each row
/** 先旋转后反转
 * [
        [ 5, 1, 9,11],          [5,2,13,15]        [15,13,2,5]
        [ 2, 4, 8,10],   =====> [1,4,3,14] =====>  [14,3,4,1]
        [13, 3, 6, 7],   =====> [9,8,6,12] =====>  [12,6,8,9]
        [15,14,12,16]           [11,10,7,16]       [16,7,10,11]
    ]
 */
//     for (let i = 0; i < n; i++) {
//         for (let j = 0; j < n / 2; j++) {
//             let tmp = matrix[i][j];
//             matrix[i][j] = matrix[i][n - j - 1];
//             matrix[i][n - j - 1] = tmp;
//         }
//     }
//     return matrix    
// }

// console.log(rotate([
//     [ 5, 1, 9,11],
//     [ 2, 4, 8,10],
//     [13, 3, 6, 7],
//     [15,14,12,16]
//   ]))


/**
 * 整数反转
 * @param {number} x
 * @return {number}
 * -321 -123
 */
// var reverse = function(x) {
//     let isNegative = x < 0 ? true :false
//     let target = (isNegative?-x:x) .toString().split("").reverse().join('');
//         target = isNegative ? -target : +target; 
//     let ourrange = target >  (Math.pow(2,31) - 1 )||  target < (Math.pow(-2,31))

//     return ourrange ? 0 : target
// };
/**
 * @param {number} x
 * @return {number}
 */
// var reverse = function(x) {
//     var n=0;
//     while(x!=0){
//         //进行计算
//         n=n*10+x%10; ///666666啊！
//         //去除待计算数字的最后一位
//         x=parseInt(x/10);

//     }
//      if(n<-Math.pow(2,31)||n>Math.pow(2,31)-1){
//             //存在溢出，则返回为0
//             return 0;
//         }
//     return n;
//  };
// reverse(-321)


/**
 * @param {string} s
 * @return {number}
 * 字符串中的第一个唯一字符
 */
// var firstUniqChar = function(s) {
//     for (let i = 0; i < s.length; i++) {
//         if (s.indexOf(s[i]) === s.lastIndexOf(s[i])) {
//             return i
//         }
//     }
//     return -1
// };
// var firstUniqChar = function(s) {
//     //map
//     let map = new Map()
//     let hash = {}
//     for(let i = 0 , len = s.length ; i< len ; i++){
//         if(hash[s[i]]){
//             map.delete(s[i])
//         }else{
//             hash[s[i]] = 1;
//             map.set(s[i],1)
//         }

//     }
//     if(map.size == 0){
//         return -1;
//     }
//     return map.values().next().value
// };

// var firstUniqChar = function(s){
//       // 解法二
//   if (s === '' || s.length < 1) {return -1;}
//   let set = new Set();
//   for (let i = 0 ;i < s.length;i++) {
//     // includes第二个参数可选。从当前字符串的哪个索引位置开始搜寻子字符串，默认值为0。
//     if (!s.includes(s[i], i + 1) && !set.has(s[i])) {
//       return i;
//     } else {
//       set.add(s[i]);
//     }
//   }
// }

// console.log(firstUniqChar('leetcode'))

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 * 有效的字母异位词
 * s = "anagram", t = "nagaram"
//  */
// var isAnagram = function(s, t) {
//     //双子针 ，map表
//     s = s.split('').sort().join("")
//     t = t.split('').sort().join("")
//     if(s === t){
//         return true
//     }
//     return false
// };

// var isAnagram = function (s, t) {
//     if (s.length !== t.length) {
//       return false;
//     }
//     const obj = {};
//     for (let i = 0; i < s.length; i++) {
//       obj[s[i]] ? obj[s[i]]++ : (obj[s[i]] = 1)
//     }
//     for (let i = 0; i < t.length; i++) {
//       if (!obj[t[i]]) {
//         return false
//       }
//       obj[t[i]]--
//       if (obj[t[i]] < 0) {
//         return false;
//       }
//     }
//     return true
//   };


// console.log(isAnagram('anagram','nagaram'))

/**
 * @param {string} s
 * @return {boolean}
 */
// var isPalindrome = function(s) {
//     s = s.replace(/[^0-9a-zA-Z]/g,'').toLowerCase(); //去除空格和符号
//     let left = 0
//     let right = s.length -1

//     while(left < right){
//         if(s[left] != s[right]){
//             return false
//         }
//         left++
//         right--
//     }
//     return true· 1
// };

// console.log(isPalindrome("race a car"))

/**
 * @param {string} str
 * @return {number}
 */
// var myAtoi = function(str) {
//     //利用正则
//     let result = str.trim().match(/^[-|+]{0,1}[0-9]+/)
//     if(result != null){

//         if(result[0] > (Math.pow(2,31) -1)){
//             return Math.pow(2,31) -1
//         }
//         if(result[0] < Math.pow(-2,31)){
//             return Math.pow(-2,31)
//         }

//         return result[0]
//     }

//     return 0
// };

// console.log(myAtoi("words and 987"))

/**
 * @param {number} n
 * @return {string}
 */
// var countAndSay = function(n) {
//     let prev = '1'
//     for(let i = 1; i < n; i++){
//         prev = prev.replace(/(\d)\1*/g, (item) =>{ //利用匹配重复项 来确定 1的重复次数 2的重复次数
//             console.log(item.length)
//             console.log(item)
//             return `${item.length}${item[0]}`
//         })
//     }
//     return prev
// };

// console.log(countAndSay(1))

// var User = {
//     count:1,
//     getcont:function(){
//         return this.count
//     }
// }

// const foo = User.getcont
// console.log(foo()) //这里this指向window

// const foo2 = User.getcont.bind(User)
// console.log(foo2())

// var foo = {
//     this.b
// }

/**
 * 考察this的指向
 */
// const Foo = (function(){
//     let index = 1
//     return function(){
//         if( this instanceof Foo){
//             this.id = index++
//         }else{
//             return {
//                 id: index++
//             }
//         }
//     }
// })()

// let a = new Foo() // a.id =1
// console.log(a)
// let b = new Foo() // b.id =2
// console.log(b)
// let c= Foo() // c.id= 3
// console.log(c)

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 * 5>4>3>2>1>null
 */
let head = new ListNode(1)
let b1 = new ListNode(1)
let c1 = new ListNode(2)
let e1 = new ListNode(1)
head.next = b1
b1.next = c1
c1.next = e1
e1.next = null

// var deleteNode = function(node) {
//     //双链表的删除 使用双指针
//     let prev = head
//     let cur = head
//     while(cur!=null){
//         if(cur.val === node){
//             prev.next = cur.next
//             return prev
//         }else{
//             prev = cur
//             cur = cur.next
//         }

//     }
// };

// console.log(deleteNode(1))

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
// var removeNthFromEnd = function(head, n) {
//     //双指针了吧， 俩个指针间隔n
//     let preHead = new ListNode(-1) //设置哨兵节点，防止头部被删除
//     preHead.next = head

//     let fast = preHead
//     let slow = preHead

//     while(n != 0){
//         fast = fast.next
//         n--
//     }

//     while(fast.next != null){
//         fast = fast.next;
//         slow = slow.next;
//     }
//     slow.next = slow.next.next;

//     return preHead.next;
// };

// console.log(removeNthFromEnd(head,2))

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// var reverseList = function(head) {
//     let prev = null
//     let curr = head

//     while(curr != null){
//         let next = curr.next;
//         curr.next = prev
//         prev = curr
//         curr = next
//     }

//     return prev
// };

// console.log(reverseList(head))

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
let l1 = new ListNode(1)
let b3 = new ListNode(2)
let c3 = new ListNode(4)

l1.next = b3
b3.next = c3
c3.next = null

let l2 = new ListNode(1)
let b2 = new ListNode(3)
let c2 = new ListNode(4)

l2.next = b2
b2.next = c2
c2.next = null
// var mergeTwoLists = function(l1, l2) {
//     let head = new ListNode(-1)
//     let prev = head //这里的prev就是一个指针，根据val的比较，在2个链表中切换，
//     while(l1 != null && l2 != null){
//         if(l1.val <= l2.val){
//             prev.next = l1
//             l1 = l1.next
//         }else{
//             prev.next = l2
//             l2 = l2.next
//         }
//         prev = prev.next;
//     }
//     //这里看看谁遍历结束了 然后把没有结束的直接拼在后面
//     prev.next = l1 == null ? l2 : l1;

//     return head.next
// };

// console.log(mergeTwoLists(l1,l2))

/**每日一题 1111 有效括号
 * @param {string} seq
 * @return {number[]}
 * 模拟栈
 */
// var maxDepthAfterSplit = function(seq) {
//     if(seq === '' || seq === null ){
//         return []
//     }
//     let len = 0
//     let res = []

//     for(let i =0; i<seq.length;i++){ // 这里也可以使用 for of来遍历字符串哦
//         if(s[i] === '('){
//              len++
//             res.push(len%2)
//         }else{
//             res.push(len%2)
// len--
//         }
//     }

//     return res
// };

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean} 234. 回文链表
 * 实现原理：找到链表的中间节点，并且反转中间之前的节点，然后与
 * 后续节点进行比较，如果不一样return false
 * 1.找到中间节点
 * 2.反转
 * 3.比较
 * 
 * 时间:o(n)
 * 空间:o(1)
 */
// var isPalindrome = function(head) {
//     if(head === null || head.next === null){
//         return true
//     }
//     let mid = head
//     let prev = null
//     let reversed = null //反转的链表
//     // end每次走两格，这个循环的时间复杂度为O(n/2)
//     while(head !== null && head.next !== null){
//         // 这个赋值要在mid被修改前提前
//         prev = mid
//         // 遍历链表
//         mid = mid.next
//         head = head.next.next
//         // 反转前面部分的节点，并用reversed保存
//         prev.next = reversed
//         reversed = prev
//     }
//     // 奇数mid往后走一位
//     if(head) mid = mid.next //这里在之前的遍历完然后还有剩，那就说明是奇数，可以不考虑中间节点

//     while(mid){
//         if(reversed.val !== mid.val){
//             return false
//         }
//         reversed = reversed.next
//         mid = mid.next
//     }
//     return true
// };

/**
 * 
 * @param {*} head 
 * 将链表转换成数组，数据判断是否是回文就很简单了
 */
// var isPalindrome = function(head) {
//     if (!head) return true;
//     let arr = []

//     while(head){
//         arr.push(head.val)
//         head = head.next
//     }

//     for(let i = 0 ,len = arr.length ; i<len ;i++){
//         if(arr[i] !== arr[len - 1 -i]){
//            return false 
//         }
//     }
//     return true
//   };
// console.log(isPalindrome(head))

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

// let l2 = new ListNode(1)
// let b2 = new ListNode(3)
// let c2 = new ListNode(4)

// l2.next = b2
// b2.next = c2
// c2.next = null

/** 判断是否是环形链表 --- 快慢指针 当快指针走到了慢指针后面就说明是环形
 * @param {ListNode} head
 * @return {boolean}
 */
// var hasCycle = function(head) {
//     let slow = head
//     let fast = head

//     while(slow != null && fast!=null){
//         let fn = fast.next
//         if(fn.val === slow.val){
//             return true
//         }
//         slow = slow.next
//         fast = fast.next.next
//     }

//     return false
// };

// console.log(hasCycle(head))

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}
/*
 * @param {TreeNode} root
 * @return {boolean}
 * 验证2叉搜索树
 */
// var isValidBST = function(root) {
//     if(root === null){
//         return true
//     }
//     const leftmax = rightest(root.left)
//     const rightmin = leftest(root.right)
//     if(leftmax&&leftmax.val>=root.val) return false
//     if(rightmin&&rightmin.val<=root.val) return false

//     return isValidBST(root.left) && isValidBST(root.right)
// };
// //获取左边的最大值
// const rightest = function(node){
//     while(node&&node.right){
//         node = node.right
//     }
//     return node
// }
// //获取右边的最小值
// const leftest = function(node){
//     while(node&&node.left){
//         node = node.left
//     }
//     return node
// }

let tree = new TreeNode(3)
tree.left = new TreeNode(5)
tree.right = new TreeNode(1)
tree.left.left = new TreeNode(6)
tree.left.right = new TreeNode(2)
tree.right.left = new TreeNode(0)
tree.right.right = new TreeNode(8)

tree.left.right.left = new TreeNode(7)
tree.left.right.right = new TreeNode(4)

// console.log(tree)
// console.log(isValidBST(tree))

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 * root = [3,5,1,6,2,0,8,null,null,7,4]
 */
// var lowestCommonAncestor = function(root, p, q) {
//     //原理是：在左边递归看看有没有pq，在右边递归看看有没有pq 如果有就返回p或q
//     if(root == null || root == p || root == q){
//         return root
//     }
//     const left = lowestCommonAncestor(root.left,p,q)
//     const right = lowestCommonAncestor(root.right,p,q)

//     return left === null ? right :right === null ? left :root
// };

// console.log(lowestCommonAncestor(tree,5,1))

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 * //2叉搜索树查看最近的公共节点 利用2叉的特点 如果 p< root && q >root 则root就为公共节点
 */
// var lowestCommonAncestor = function(root, p, q) {
//     if(q.val < root && p.val <root){
//         return lowestCommonAncestor(root.left,p,q)
//     }
//     if(q.val > root && p.val >root){
//         return lowestCommonAncestor(root.right,p,q)
//     }

//     return root
// };
/**
 * 
 * 2叉搜索树在中序遍历的时候会遍历出来有序的且升序的一棵树[1,2,3,4,5,6]
 */

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 * //递归题目---》分治o(log n)
 * 动态规划
 */

// var myPow = function(x,n){
//     if(n<0) return 1/ myPow(x,-n)
//     if(n === 0) return 1 //利用任何树的0次方作为递归的边界
//     if(n%2===0) return myPow(x*x,Math.floor(n/2)) //n为偶数
//     return myPow(x*x,Math.floor(n/2)*x) //n为奇数
// }

// var myPow = function(x,n){
//     if(n<0){
//         x = 1 / n
//         n = -n
//     }
//     let pow = 1

//     while(n){
//         if(n&&1){
//             pow *= n
//         }
//         x*=x
//         n>>=1
//     }
//     return pow
// }

// var isValid = function(s) {
//     let map = {
//         "(":")",
//         "[":"]",
//         "{":"}"
//     }
//     if(s.length === 1 || s.length === 0){
//         return false
//     }
//     let stack = []
//     for(let i=0,len = s.length; i<len;i++){
//         if(map[s[i]] !== undefined){
//             stack.push(s[i])
//         }else{
//             if(stack.pop !== s[i]){
//                 return false
//             }
//         }
//     }
//     return true
// };

// isValid("()")

/**
 * 
 * @param {*} name 
 * @param {*} color 
 * 请手写实现 ES5 中 Function 原型的 bind（即手写下面代码块中的myBind）方法，
 * 使得以下程序最后能输出 'success'。
 */


/**
 * 首先bind第一步还是this的指向
 */
//   Function.prototype.myApply = function(context,args){
//     context = context || window
//     args = args || []
//     let key = Symbol()
//     context[key] = this //this绑定
//     let result = context[key](...args)
//     delete context[key]
//     return result 
//   }


//   Function.prototype.myBind = function(context,...arg1){
//     if(typeof this !== 'function'){ // 这里只能让函数调用
//         throw new TypeError('not a function!!')
//     }
//     let fn = this
//     function newFN (...arg2){
//         const args = arg1.concat(arg2);
//         let isNew = this instanceof newFN //定this的指向
//         return fn.myApply(isNew?this:context,args)
//     }
//     newFN.prototype = Object.create(fn.prototype);
//     newFN.prototype.constructor = newFN

//     return newFN
//   }

//   function Animal(name, color) {
//     this.name = name;
//     this.color = color;
//   }
//   Animal.prototype.say = function () {
//     return `I'm a ${this.color} ${this.name}`;
//   };
//   const Cat = Animal.myBind(null, 'cat');
//   const cat = new Cat('white'); 

//   console.log(Cat)
//   if (cat.say() === 'I\'m a white cat' && cat instanceof Cat && cat instanceof Animal) {
//     console.log('success');
//   }

//   function sum(a, b, c) {
//     return a + b + c;
//   }

//   const sum10 = sum.myBind(null, 10);
//   let jing = sum10(20, 30);
//   console.log(jing)

/**
 * 创建一个新对象
 * 获取构造器
 * 链接原型
 * 绑定this
 * 输出一个新的对象
 */
// function _new(fn){
//     let  obj = {}
//     let result = fn.apply(obj,[].slice.call(arguments,1)) //第一个参数的构造函数，第二个是参数
//     return result instanceof Object ? result:obj
// }

// function _new(fn,...arg){
//     let obj = Object.create(fn.prototype) //链接原型
//     const ret = fn.apply(obj, arg); //改变this的指向
//     return ret instanceof Object ? ret : obj;
// }

// function _new(fn,...arg){
//     let obj = {}
//     let con = [].slice.call(arguments)
//     obj.__proto__ = con.prototype //链接原型
//     const ret = fn.call(obj, ...arg); //改变this的指向
//     return ret instanceof Object ? ret : obj;
// }

// function Con(a,b,c) {
//     this.a = a;
//     this.b = b
//     this.c = c
// }
// const obj = _new(Con, 1,2,3);

// console.log(obj)

// function deepCopy3(obj) {
// hash表，记录所有的对象的引用关系
// let map = new WeakMap();
// function dp(obj) {
//     let result = null;
//     let keys = Object.keys(obj);
//     let key = null,
//         temp = null,
//         existobj = null;

//     existobj = map.get(obj);
// //如果这个对象已经被记录则直接返回
// if(existobj) {
//     return existobj;
// }

// result = {}
// map.set(obj, result);

//         for(let i =0,len=keys.length;i<len;i++) {
//             key = keys[i];
//             temp = obj[key];
//             if(temp && typeof temp === 'object') {
//                 result[key] = dp(temp);
//             }else {
//                 result[key] = temp;
//             }
//         }
//         return result;
//     }
//     return dp(obj);
// }

// const obj= {
//     a: {
//         name: 'a'
//     },
//     b: {
//         name: 'b'
//     },
//     c: {

//     }
// };
// obj.c = obj.a;

// const copy = deepCopy3(obj);

/**
 * 节流/防抖
 */
//节流1
//  function throttle(fn,wait){
//     let time = Date.now()
//     return function(){
//         let now = Date.now()
//         let context = this
//         if( now - time >= wait ){
//             let arg = [].slice.call(arguments,1)
//             fn.apply(context,arg)
//             time = Date.now()
//         }
//     }
//  }
//节流2
// var throttle = function(func, delay) {
//     var prev = Date.now();
//     return function() {
//         var context = this;
//         var args = arguments;
//         var now = Date.now();
//         if (now - prev >= delay) {
//             func.apply(context, args);
//             prev = Date.now();
//         }
//     }
// }
// let fn1 = function(val){
//     this.name = val
//     console.log(`11${this.name}`)
// }
// let aa = throttle(fn1,100)

// aa(11)
// aa(22)

//防抖

// var debounce = function(fn,wait){
//     let time = null
//     return function(){
//         if(time) clearTimeout(time);
//         let context = this
//         let args = arguments
//         time = setTimeout(function(){
//             fn.apply(context,args)
//         },wait)
//     }
// }

// let bb = debounce(fn1,1000)
// bb(11)
// bb(11)


// function A(name) {
//     this.name = name;
// }
// A.prototype.log = function() {
//     //每隔2s输出一下name
//     setTimeout(() => {
//         console.log(this.name)
//     }, 200);
// }

// let a1 = new A(12)
// a1.log()
// console.log(a1)

// function fo(){
//     console.log(123)
//     setTimeout(() => {
//       fo()  
//     }, 0);
// }
// fo()
// let foo = function(){
//     let chat
// }
// window.requestAnimationFrame = foo()

let arr = [1, [1, 2],
  [1, 2, 3]
]

// while(arr.some(Array.isArray)){
//     arr = [].concat(...arr)
// }

// let flat = function(arr){
//     return arr.reduce(function(prev,cur){
//         return prev.concat(cur instanceof Array ? flat(cur) : cur)
//     },[])
// }

// arr = flat(arr)

// console.log(arr)

//手写继承
// 父类
function Parent() {
  this.name = '写代码像蔡徐抻'
}
// 父类的原型方法
// Parent.prototype.getName = function() {
//     console.log(this.name)
// }
// // 子类
// function Child() {}

// // 让子类的原型对象指向父类实例, 这样一来在Child实例中找不到的属性和方法就会到原型对象(父类实例)上寻找
// Child.prototype = new Parent()
// Child.prototype.constructor = Child // 根据原型链的规则,顺便绑定一下constructor, 这一步不影响继承, 只是在用到constructor时会需要

// // 然后Child实例就能访问到父类及其原型上的name属性和getName()方法
// const child = new Child()
// child.name          // '写代码像蔡徐抻'
// child.getName()     // '写代码像蔡徐抻

// console.log(child)

// function Parent(name) {
//     this.name = [name]
// }
// Parent.prototype.getName = function() {
//     console.log(this.name)
// }
// function Child(val) {
//     Parent.call(this, val)   // 执行父类构造方法并绑定子类的this, 使得父类中的属性能够赋到子类的this上
// }
// Child.prototype = new Parent()
// Child.prototype.constructor = Child 
// //测试
// const child1 = new Child()
// const child2 = new Child('zhangshan')
// child1.name[0] = 'foo'
// child2.getName()
// child1.getName()


//手写一个冒泡
// function bubbleSort(arr){
//     for(let i = arr.length-1; i>0 ;i--){
//         for(let j=0; j<i;j++){
//             //交换
//             if(arr[i]<arr[j]){
//                 let temp = arr[i]
//                 arr[i] = arr[j]
//                 arr[j] = temp
//             }
//         }
//     }
//     return arr
// }

// console.log(bubbleSort([3,1,2,6,9]))

//优化一个冒泡排序

// function bubbleSort2(arr){
//     for(let i = arr.length -1 ; i >0 ;i --){
//         for(let j = 0 ; j< i; j++){
//             //交换
//             if(arr[i]<arr[j]){
//                 flag = false
//                 let temp = arr[i]
//                 arr[i] = arr[j]
//                 arr[j] = temp
//             }
//         }
//     }
//     return arr
// }
// console.log(bubbleSort2([3,1,2,6,9]))

// const foo = {
//     bar: 10,
//     fn: function() {
//        console.log(this)
//        console.log(this.bar)
//     }
// }

// var fn1 = foo.fn

// fn1()

// function foo() {
//     return a => {
//         console.log(this.a)
//     };
// }

// const obj1 = {
//     a: 2
// }

// const obj2 = {
//     a: 3
// }

// const bar = foo.call(obj1) //箭头函数指向obj1 ==》2
// console.log(bar.call(obj2)) //箭头函数绑定一次就无法更改了 ==》2

/**
 * 实现一个bind
 */

// Function.prototype.mybind2 = function(context,...arg1){
//     let fn = this
//     return function newFn(...arg2){
//         let arg = [...arg1,...arg2]
//         let isnew = this instanceof newFn
//         return fn.apply(isnew?this:context,arg)
//     }
// }

// function red() {
//     console.log('red');
// }
// function green() {
//     console.log('green');
// }
// function yellow() {
//     console.log('yellow');
// }

// async function async1() {
//     console.log('async1 start') // step 4: 直接打印同步代码 async1 start
//     await async2() // step 5: 遇见 await，首先执行其右侧逻辑，并在这里中断 async1 函数
//     console.log('async1 end') // step 11: 再次回到 async1 函数，await 中断过后，打印代码 async1 end
// }

// async function async2() {
//     console.log('async2') // step 6: 直接打印同步代码 async2，并返回一个 resolve 值为 undefined 的 promise
// }

// console.log('script start') // step 1: 直接打印同步代码 script start

// step 2: 将 setTimeout 回调放到宏任务中，此时 macroTasks: [setTimeout]
// setTimeout(function() {            
//     console.log('setTimeout') // step 13: 开始执行宏任务，输出 setTimeout
// }, 0)  

// async1() // step 3: 执行 async1 

// // step 7: async1 函数已经中断，继续执行到这里
// new Promise(function(resolve) {
//     console.log('promise1') // step 8: 直接打印同步代码 promise1
//     resolve()
// }).then(function() { // step 9: 将 then 逻辑放到微任务当中
//     console.log('promise2') // step 12: 开始执行微任务，输出 promise2
// })

// console.log('script end') 

// var name = 'zcy'
// const person = {
//     name: 'lucas',
//     getName: ()=> {
//       console.log(this.name)
//     }
//   };
//   person.getName()


//创建Promise对象x1，并在executor函数中执行业务逻辑

/**
 * 
 * @param {*} value 
 * 
 * let x1 = new Promise((resolve, reject)=>{
 *      resolve(100)
 * }).then((value)=>{
 *      console.log(value)
 * })
 */

// x1延迟绑定回调函数onResolve


/**
 * 手写一个Promise
 */

// var PENDING = 'pending'
// var RESOLVED = 'resolved'
// var REJECTED = 'rejected'

// function Bromise(fn){ //构造器中的方法，同步执行
//     let that = this
//     that.state = PENDING
//     /**
//      * 用于保存 then 中的回调，
//      * 因为当执行完 Promise 时状态可能还是等待中，
//      * 这时候应该把 then 中的回调保存起来用于状态改变时使用
//      */
//     that.resolvedCallbacks=[] 
//     that.rejectedCallbacks=[]
//     that.value = null

//     function resolve(value){
//         if(value instanceof Bromise){
//             value.then(resolve, reject)
//         }
//         setTimeout(function(){
//             if(that.state === PENDING){
//                 that.state = RESOLVED
//                 that.value = value
//                 that.resolvedCallbacks.map(cb=>cb(that.value))
//             }
//         },0)

//     }

//     function reject(){
//         setTimeout(function(){
//             if(that.state === PENDING){
//                 that.state = REJECTED
//                 that.value = value
//                 that.rejectedCallbacks.map(cb=>cb(that.value))
//             }
//         },0)
//     }

//利用trycatch来区别Resolve，reject
//     try{
//         fn(resolve, reject)
//     }catch(e){
//         reject(e)
//     }
// }

// Bromise.prototype.then = function(onFulfilled,onRejected){
//     //也要判断当前是什么状态,把对应的callback丢入
//     const that = this
//     //首先判断两个参数是否为函数类型，因为这两个参数是可选参数
//     //当参数不是函数类型时，需要创建一个函数赋值给对应的参数，
//     //同时也实现了透传，比如如下代码 (透传。这里也是为什么error会传到底部把)
//     onFulfilled = typeof onFulfilled === 'function' ? onFulfilled : v => v
//     onRejected =  typeof onRejected === 'function' ? onRejected : r => { throw r}

/**
 * 接下来就是一系列判断状态的逻辑，当状态不是等待态时，就去执行相对应的函数。
 * 如果状态是等待态的话，就往回调函数中 push 函数，比如如下代码就会进入等待态的逻辑
 * new MyPromise((resolve, reject) => {
        setTimeout(() => {
            resolve(1)
        }, 0)
    }).then(value => {
        console.log(value)
    })
 */
//     if(that.state === PENDING){
//         /**
//          * 首先我们返回了一个新的 Promise 对象，并在 Promise 中传入了一个函数
//          * 函数的基本逻辑还是和之前一样，往回调数组中 push 函数
//          * 同样，在执行函数的过程中可能会遇到错误，所以使用了 try...catch 包裹
//          * 规范规定，执行 onFulfilled 或者 onRejected 函数时会返回一个 x，
//          * 并且执行 Promise 解决过程
//          * 这是为了不同的 Promise 都可以兼容使用，比如 JQuery 的 Promise 能兼容 ES6 的 Promise
//          */
//         return (promise2 = new Bromise((resolve, reject)=>{
//             that.resolvedCallbacks.push(()=>{
//                 try{
//                     const x = onFulfilled(that.value)
//                     resolutionProcedure(promise2, x, resolve, reject)
//                 }catch(r){
//                     reject(r)
//                 }
//             })

//             that.rejectedCallbacks.push(()=>{
//                 try{
//                     const x = onRejected(that.value)
//                     resolutionProcedure(promise2, x, resolve, reject)
//                 }catch(r){
//                     reject(r)
//                 }
//             })
//         }))
//     }

//     if(that.state === RESOLVED){
//         return ( promise2 = new Bromise((resove,reject)=>{
//             setTimeout(function(){
//                 try{
//                     const x = onFulfilled(that.value)
//                     resolutionProcedure(promise2,x,resolve,reject)
//                 }catch(r){
//                     reject(r)
//                 }

//             },0)
//         }))

//     }

//     if(that.state === REJECTED){
//         return ( promise2 = new Bromise((resove,reject)=>{
//             setTimeout(function(){
//                 try{
//                     const x = onRejected(that.value)
//                     resolutionProcedure(promise2,x,resolve,reject)
//                 }catch(r){
//                     reject(r)
//                 }
//             },0)
//         }))
//     }

//     function resolutionProcedure(promise2, x, resolve, reject) {
//         //首先规范规定了 x 不能与 promise2 相等，这样会发生循环引用的问题，比如如下代码
//         if (promise2 === x) {
//           return reject(new TypeError('Error'))
//         }
//         /**
//          * 然后需要判断 x 的类型
//          * 这里的代码是完全按照规范实现的。如果 x 为 Promise 的话，需要判断以下几个情况：
//          * 如果 x 处于等待态，Promise 需保持为等待态直至 x 被执行或拒绝
//          * 如果 x 处于其他状态，则用相同的值处理 Promise
//          */
//         if (x instanceof Bromise) {
//             x.then(function(value) {
//                 resolutionProcedure(promise2, value, resolve, reject)
//             }, reject)
//         }

//         //首先创建一个变量 called 用于判断是否已经调用过函数
//         let called = false
//         //然后判断 x 是否为对象或者函数，如果都不是的话，将 x 传入 resolve 中
//         if (x !== null && (typeof x === 'object' || typeof x === 'function')) {
//             try{
//                 //如果 x 是对象或者函数的话，先把 x.then 赋值给 then，
//                 let then = x.then
//                 //然后判断 then 的类型，
//                 //如果 then 是函数类型的话，
//                 //就将 x 作为函数的作用域 this 调用之，
//                 //并且传递两个回调函数作为参数，
//                 //第一个参数叫做 resolvePromise ，
//                 //第二个参数叫做 rejectPromise，
//                 //两个回调函数都需要判断是否已经执行过函数，然后进行相应的逻辑
//                 if (typeof then === 'function') {
//                     then.call(
//                         x,
//                         y=>{
//                             if (called) return
//                             called = true
//                             resolutionProcedure(promise2, y, resolve, reject)
//                         },
//                         e=>{
//                             if (called) return
//                             called = true
//                             reject(e)
//                         }
//                     )
//                 }else{
//                     //如果不是函数类型的话，就将 x 传入 resolve 中
//                     resolve(x)
//                 }
//             }catch(e){
//                 //以上代码在执行的过程中如果抛错了，将错误传入 reject 函数中
//                 if (called) return
//                 called = true
//                 reject(e)
//             }
//         }else {
//             resolve(x)
//           }
//       }
// }

// function executor(resolve, reject){
//     resolve(100)
// }
// let x1 = new Bromise(executor)//promise构造函数中是同步执行的，then里的是异步的

// function onResolve(value){
//     console.log(value)
// }
// x1.then(onResolve)

// let p1 = new Promise((resolve, reject) => {
//     resolve('成功了')
//   })

//   let p2 = new Promise((resolve, reject) => {
//     resolve('success')
//     console.log('执行了2')
//   })

//   let p3 = Promise.reject('失败')

//   Promise.all([p1, p2]).then((result) => {
//     console.log(result)               //['成功了', 'success']
//   }).catch((error) => {
//     console.log(error)
//   })

//   Promise.all([p1,p3,p2]).then((result) => {
//     console.log(result)
//   }).catch((error) => {
//     console.log(error)      // 失败了，打出 '失败'
//   })

//   let wake = (time) => {
//     return new Promise((resolve, reject) => {
//       setTimeout(() => {
//         resolve(`${time / 1000}秒后醒来`)
//       }, time)
//     })
//   }

//   let p1 = wake(3000)
//   let p2 = wake(2000)

//   /**
//    * 需要特别注意的是，
//    * Promise.all获得的成功结果的数组里面的数据顺序和Promise.all接收到的数组顺序是一致的，
//    * 即p1的结果在前，即便p1的结果获取的比p2要晚。
//    * 这带来了一个绝大的好处：在前端开发请求数据的过程中，
//    * 偶尔会遇到发送多个请求并根据请求顺序获取和使用数据的场景，使用Promise.all毫无疑问可以解决这个问题。
//    * 数组怎么接受的，返回就是怎么返回的，保持了顺序
//    */
//   Promise.all([p1, p2]).then((result) => {
//     console.log(result)       // [ '3秒后醒来', '2秒后醒来' ]
//   }).catch((error) => {
//     console.log(error)
//   })

// let p1 = new Promise((resolve, reject) => {
//     setTimeout(() => {
//       resolve('success')
//     },1000)
//   })

//   let p2 = new Promise((resolve, reject) => {
//     setTimeout(() => {
//       reject('failed')
//     }, 1500)
//   })

//   Promise.race([p1, p2]).then((result) => {
//     console.log(result)
//   }).catch((error) => {
//     console.log(error)  // 打开的是 'failed'
//   })


//foo函数
// function* foo() {
//     let response1 = yield fetch('https://www.geekbang.org')
//     console.log('response1')
//     console.log(response1)
//     let response2 = yield fetch('https://www.geekbang.org/test')
//     console.log('response2')
//     console.log(response2)
// }

// //执行foo函数的代码
// let gen = foo()
// function getGenPromise(gen) {
//     return gen.next().value
// }
// getGenPromise(gen).then((response) => {
//     console.log('response1')
//     console.log(response)
//     return getGenPromise(gen)
// }).then((response) => {
//     console.log('response2')
//     console.log(response)
// })


// async function foo() {
// console.log(1)
/**
         * await 100 ===> let promise_ = new Promise((resolve,reject){
         resolve(100)
    })
    /**
     * 然后 JavaScript 引擎会暂停当前协程的执行，
     * 将主线程的控制权转交给父协程执行，同时会将 promise_ 对象返回给父协程。
     * 主线程的控制权已经交给父协程了，这时候父协程要做的一件事是调用 promise_.then 来监控 promise 状态的改变。
     * 接下来继续执行父协程的流程，这里我们执行console.log(3)，并打印出来 3。
     * 随后父协程将执行结束，在结束之前，
     * 会进入微任务的检查点，然后执行微任务队列，
     * 微任务队列中有resolve(100)的任务等待执行，
     * 执行到这里的时候，会触发 promise_.then 中的回调函数，如下所示：
     * promise_.then((value)=>{ //回调函数被激活后 //将主线程控制权交给foo协程，并将vaule值传给协程})
        foo 协程激活之后，会把刚才的 value 值赋给了变量 a，
        然后 foo 协程继续执行后续语句，执行完成之后，将控制权归还给父协程。
//      */
//     let a = await 100
//     console.log(a)
//     console.log(2)
// }
// console.log(0)
// foo()
// console.log(3)


// async function foo() {
//     console.log('foo')
// }
// async function bar() {
//     console.log('bar start')
//     await foo()
//     console.log('bar end')
// }
// console.log('script start')
// setTimeout(function () {
//     console.log('setTimeout')
// }, 0)
// bar();
// new Promise(function (resolve) {
//     console.log('promise executor')
//     resolve();
// }).then(function () {
//     console.log('promise then')
// })
// console.log('script end')


/**
 * 二叉树的最大深度
 * */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 * 递归
 */
// var maxDepth = function(root) {
//     if(!root){
//         return 0
//     }else{
//         let left = maxDepth(root.left)
//         let right = maxDepth(root.right)
//         return Math.max(left,right)+1
//     }
// };

// console.log(maxDepth(tree))

/**
 * 验证2叉搜索树
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
// var isValidBST = function(root) {
//     if(!root) return true
//     if (root.left && root.val <= root.left.val) return false
//     if (root.right && root.val >= root.right.val) return false;
//     return isValidBST(root.left) &&isValidBST(root.right)
// };



// var isValidBST = function(root) {
//     const arr = tree2Arr(root);
//     for (let i = 0; i < arr.length - 1; i++) {
//       if (arr[i + 1] <= arr[i]) return false;
//     }
//     return true;
//   };

//   function tree2Arr(root) {
//     return root ? tree2Arr(root.left).concat(root.val, tree2Arr(root.right)) : [];
//   }


// var isValidBST = function(root, pre = null, next = null) {
//     if (!root) return true;
//     // 在这里打印日志可以很好的观察到遍历顺序以及每个节点到底与哪些上下限进行了比较
//     console.log(root && root.val, pre && pre.val, next && next.val);
//     if (pre && pre.val >= root.val) return false;
//     if (next && next.val <= root.val) return false;
//     return isValidBST(root.left, pre, root) && isValidBST(root.right, root, next);
//   };

//   console.log(isValidBST(tree))

//删除排序数组中的重复项 [1,1,2,2,2,3] 
// var removeDuplicates = function(nums) {
//   return Array.from(new Set(nums))
// }


// var removeDuplicates = function(nums) {
//   if (nums.length == 0) return 0
//   let i = 0
//   for (let j = 0; j < nums.length; j++) {
//     if (nums[i] !== nums[j]) {
//       i++
//       nums[i] = nums[j]
//     }
//   }
//   return i + 1
// }

// console.log(removeDuplicates([1, 1, 2]))

/**
 * 买卖股票的最佳时机 II
 * 
 */

/**
 * @param {number[]} prices
 * @return {number}
 * [7,1,5,3,6,4]
 */
// var maxProfit = function(prices) {
//   //   //当我发现今天的价格比明天的高的时候就要卖掉了
//   let max = 0;
//   let cur = 0;
//   let temp = 0
//   for (let i = 0, len = prices.length; i < len; i++) {
//     //如果当前的价格比手上的高卖出，当前没有则买入
//     let min = Math.min(prices[i], prices[i + 1]) || 0
//     if (cur === 0 && min) {
//       cur = min
//     } else if (prices[i] > prices[i + 1] || prices[i] === prices[len - 1]) {
//       max += prices[i] - cur
//       cur = 0
//     }

//   }
//   return max
// };
// console.log(maxProfit([1, 2, 3, 4, 5]))

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 * [1,2,3,4,5,6,7] 和 k = 3
 * [5,6,7,1,2,3,4]
 * splice(起始索引，个数，值)
 */
// var rotate = function(nums, k) {
//   nums.splice(0, 0, ...nums.splice(nums.length - k, k))
//   return nums
// };

// console.log(rotate([1, 2, 3, 4, 5, 6, 7], 3))

/**
 * @param {number[]} nums
 * @return {boolean}
 * 给定一个整数数组，判断是否存在重复元素。
    如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
 */
// var containsDuplicate = function(nums) {
//   //map表
//   let map = new Map()
//   for (let i = 0; i < nums.length; i++) {
//     if (map.has(nums[i])) {
//       return true
//     }
//     map.set(nums[i])
//   }
//   return false
// };
// console.log(containsDuplicate([1, 2, 3]))

/**
 * 只出现一次的数字
 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
 * 说明：
    你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
    原地修改，把相同的删掉，留下不同的
    [2,2,1]
 */
// /**
//  * @param {number[]} nums
//  * @return {number}
//  */
// var singleNumber = function(nums) {
//   let map = new Map()
//   for (let i = 0; i < nums.length; i++) {
//     if (map.has(nums[i])) {
//       let t = map.get(nums[i])
//       nums[i] = ''
//       nums[t] = ''
//     } else {
//       map.set(nums[i], i)
//     }
//   }
//   return nums
// };

// console.log(singleNumber([4, 1, 2, 1, 2]))

// var removeDuplicates = function(nums) {
//   let set = new Set()
//   for (let i = 0; i < nums.length; i++) {
//     if (!set.has(nums[i])) {
//       set.add(nums[i])
//     }
//   }

//   return Array.from(set)
// };

// console.log(removeDuplicates([1, 1, 2]))

// var maxArea = function(height) {
//   //双子针
//   let max = 0
//   let i = 0
//   let j = height.length - 1
//   while (i < j) {
//     let w = j - i
//     let h = Math.min(height[i], height[j])
//     let temp = w * h
//     if (temp > max) {
//       max = temp
//     }
//     if (height[i] < height[j]) {
//       i++
//     } else {
//       j--
//     }
//   }
//   return max
// };
// console.log(maxArea([1, 1]))

// var findMedianSortedArrays = function(nums1, nums2) {
//   //合并排序？
//   let arr = nums1.concat(nums2).sort((a, b) => {
//     return a - b
//   })
//   let index = 0
//   let mid
//   if (arr.length % 2 == 0) {
//     // 偶数   
//     index = parseFloat(arr.length / 2)
//     mid = (arr[index] + arr[index - 1]) / 2
//   } else {
//     // 奇数 
//     index = parseInt(arr.length / 2)
//     mid = arr[index]
//   }
//   return mid
// }
// console.log(findMedianSortedArrays([1, 3], [2]))

// var threeSum = function(nums) {
//     //双子针
//     let i = 0
//     let j = 1
//     let len = nums.length
//     let result = []
//     let map = new Map()
//     while (j < len) {
//       let temp = -(nums[i] + nums[j])
//       let index = nums.indexOf(temp)
//     if (index > -1 && map.has(nums[temp])) {
//       result.push([nums[i], nums[j], temp])
//       map.set(nums[i])
//       map.set(nums[j])
//     }
//     i++
//     j++
//   }

//   return result
// };

// console.log(threeSum([-1, 0, 1, 2, -1, -4]))

// var maxSubArray = function(nums) {
//   let pre = 0,
//     maxAns = nums[0];
//   nums.forEach((x) => {
//     pre = Math.max(pre + x, x);
//     maxAns = Math.max(maxAns, pre);
//   });
//   return maxAns;
// };

// var maxSubArray = function(nums) {
//   let pre = 0
//   let sum = 0
//   for (let i = 0, len = nums.length; i < len; i++) {
//     pre = Math.max(nums[i] + pre, nums[i])
//     sum = Math.max(pre, sum)
//   }
//   return sum
// };

// console.log(maxSubArray([-2, -1, 1, 1, 3, 5, -5]))

// var isAnagram = function(s, t) {
//   //字母排序
//   if(s.length !== t.length){
//       return false
//   }
//   let map = {}
//   for(const k of s){
//       map[k] = map[k] || 0
//       map[k]+=1
//   }
//   for(const k of t){
//       if(!map[k]){
//           return false
//       }
//       map[k] -=1
//   }

//   return true

// };

// isAnagram('anagram','nagaram')

// var throttle = function (fn,wait){
//     let time = Date.now();
//     return function(){
//         let now = Date.now();
//         let arg = arguments || []
//         let context = this
//         if(now-time>=wait){
//             fn.apply(context,arg)
//             time = now
//         }
//     }
// }
// var myAtoi = function(str) {
//     //正则匹配/[^(-){1}[0-9]*]/
//     str = str.trim().match(/^(-){0,1}[0-9]*/)[0]
//     if(Number(str) > 2147483647){
//         return 2147483647
//     }
//     if(Number(str)< -2147483648){
//         return -2147483648
//     }
//     if(isNaN(Number(str))){
//         return 0
//     }
//     return str
// };
// myAtoi('+1')

// var countAndSay = function(n) {
//     if(n === 1){
//         return 1
//     }
//     const prev = countAndSay(n-1)

//     return prev.replace(/(\d)\1*/g,(item)=>{
//         item => `${item.length}${item[0]}`
//     })
// };
// countAndSay(4)

// var firstUniqChar = function(s) {
//   let map = {}

//   for (let i = 0, len = s.length; i < len; i++) {
//     map[s[i]] = map[s[i]] || 0
//     map[s[i]] += 1
//   }

//   for (const k in map) {
//     console.log(k)
//     if (map[k] === 1) {
//       return map[k]
//     }
//   }
//   return -1

// };

// console.log(firstUniqChar('leetcode'))

// var strStr = function(haystack, needle) {

// };

// strStr('hello', 'll')

var longestCommonPrefix = function(strs) {
  let temp = strs[0]
  if (strs.length === 0) {
    return ''
  }
  if (strs.length === 1) {
    return temp
  }
  for (let i = 0; i < strs.length; i++) {
    let j = 0
    while (j < temp.length && strs[i].length) {
      if (temp[j] != strs[i][j]) {
        break
      }
      j++
    }
    temp = temp.substr(0, j)
  }
  return temp
};

console.log(longestCommonPrefix(['aa', 'ab']))

var longestPalindrome = function(s) {
  let result = 0
  let str = ''
  for (let i = 0; i < s.length; i++) {
    let last = s.lastIndexOf(s[i])
    if (last > 0 && last > result) {
      str = s.substr(i, last)
      result = last - i
    }
  }

  return str
};
longestPalindrome('babad')